84. Largest Rectangle in Histogram

Hard

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

Example:

Input: [2,1,5,6,2,3]
Output: 10

1. Brute force

class Solution:
    def largestRectangleArea(self, h: List[int]) -> int:
        ans = 0
        for cur in range(len(h)):
            for l in range(cur,-1,-1):
                if h[l] < h[cur]:
                    l += 1
                    break
            for r in range(cur, len(h)):
                if h[r] < h[cur]:
                    r -= 1
                    break
            area = h[cur] * (r-l+1)
            ans = max(area, ans)
        return ans

时间复杂度 O（n^2）

2. pruning optimize

   参考这里，跟原始的暴力方法差不多，用i代表选择数列的end，然后用j去向前便利，找到局部最小高度和最大面积，更新minHi，和res。但是这次进行了剪枝优化，不是每一个i都要重复计算一次，只计算有可能会有更大面积的高度，即题目里的2，6，3（因为他们都比后一列高），如果这一列比后一列低，那么这一列所能产生的最大高度，一定被后一列给计算到，所以就可以省略这一步。

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        if not heights: return 0
        res = 0
        for i in range(len(heights)):
            if i+1 < len(heights) and heights[i] <= heights[i+1]:
                continue
            minHi = heights[i]
            for j in range(i, -1, -1):
                minHi = min(minHi, heights[j])
                area = minHi * (i-j+1)
                res = max(res, area)
                
        return res

3. 递增栈

   这里讲解得很好了。首先对于栈的选择，为什么使用递增栈而不是递减栈，因为为了解决题目，我们需要同时记录连续的长度，最矮的矩形。当使用单调栈时，我们为了保证栈中的元素的单调性，我们会pop出一些元素，再也不加进来

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = []
        res = 0
        i = 0
        heights.append(-1)
        cur = None
        while(i < len(heights)):
            # print(stack, res, i, cur)
            if (not stack or heights[stack[-1]] < heights[i]):
                stack.append(i)
                i += 1
            else:
                cur = stack.pop()
                if stack: 
                    curArea = heights[cur] * (i - stack[-1] - 1) # why not cur?
                else: 
                    curArea = heights[cur] * i
                res = max(res, curArea)
            
             
        return res

Why not cur: 重点，之前就是这没搞明白，导致一直有bug。我之前一直认为stack[-1] + 1 == cur，然后发现大错特错，因为为了维护单调栈，有些元素是会pop出去，然后再也不加进来的所以cur和stack[-1]并不是连续的，所以说 stack[-1] + 1 不一定等于 cur， stack[-1] + 1保证了被pop出去的元素也会参与长度的计算，不过这些话可能只有犯过和我一样错的人才能理解吧！总而言之，还是自己对单调栈理解不熟，才会有这样bug。

时间复杂度：O(n)，因为对于每个柱子只会经历入栈出栈，所以最多 2n 次

空间复杂度：O(n)，栈的大小